A portion of the disclosure of this patent document contains material that is subject to copyright protection. The copyright owner has no objection to the facsimile reproduction by anyone of the patent document or the patent disclosure, as it appears in the Patent and Trademark Office patent file or records, but otherwise reserves all copyright rights whatsoever.
The present invention relates to layout of node-link structures.
Fairchild, K. M., Poltrock, S. E., and Furnas, G. W., "SemNet: Three-Dimensional Graphic Representations of Large Knowledge Bases," in Guindon, R., Ed., Cognitive Science and its Application for Human Computer Interaction, Lawrence Erlbaum, Hillsdale, N.J., 1988, pp. 201-233, describe SemNet, a three-dimensional graphical interface. SemNet presents views that allow users to examine local detail while maintaining a global representation of the rest of a knowledge base. SeroNet also provides semantic navigation techniques such as relative movement, absolute movement, and teleportation.
As shown and described in relation to FIG. 1-1, SemNet represents a knowledge base as a directed graph in a three-dimensional space, with elements of knowledge represented as labeled rectangles connected by lines or arcs. Page 207 notes the problem of assigning positions to knowledge elements so that the organization or structure of the knowledge base is maximally apparent to the user, and indicates that, while a general solution probably does not exist, a knowledge base may contain information that can be used to compute effective positions or a user may have information allowing the user to assign effective positions. Section 3.1 describes how mapping functions can map properties of elements to positions in three-dimensional space; section 3.2, on pages 209-213, describes proximity based functions, including multidimensional scaling and heuristics, that move related knowledge elements close together and unrelated knowledge elements far apart, and section 3.3, on pages 213-214, describes personalized positioning in which a user moves knowledge elements to positions, which can be combined with other positioning techniques.
Pages 214-222 describe strategies for large knowledge bases. Section 4.1 describes fisheye viewing strategies, including fisheye views from clusters, from three-dimensional point perspective, and from sampling density. Section 4.2 describes strategies for displaying arcs. Pages 223-228 describe navigation and browsing, including recognizing locations and controlling location, such as by relative movement, absolute movement, teleportation, hyperspace movement, and moving the space.